package com.yiwenup.struct._06_graph;

import com.yiwenup.sample.Data;
import com.yiwenup.struct._06_graph.base.Graph;

import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {

    public static final Graph.WeightManager<Double> weightManager = new Graph.WeightManager<Double>() {
        @Override
        public int compare(Double w1, Double w2) {
            return w2.compareTo(w1);
        }

        @Override
        public Double add(Double w1, Double w2) {
            return w1 + w2;
        }
    };

    /**
     * 有向图
     */
    private static Graph<Object, Double> directedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
            }
        }
        return graph;
    }

    /**
     * 无向图
     */
    private static Graph<Object, Double> undirectedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
                graph.addEdge(edge[1], edge[0]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
                graph.addEdge(edge[1], edge[0], weight);
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // test1();
        // testBfs();
        // testDfs();
        // testTopo();
        // testMST();
        // testShortestPaths();
        testShortestPathInfos();
    }

    private static void testShortestPathInfos() {
        Graph<Object, Double> graph = undirectedGraph(Data.SP);
        Map<Object, Graph.PathInfo<Object, Double>> sp = graph.shortestPathInfo("A");
        sp.forEach((vertex, pathInfo) -> {
            System.out.println(vertex + " => " + pathInfo);
        });
    }

    private static void testShortestPaths() {
        Graph<Object, Double> graph = undirectedGraph(Data.SP);
        Map<Object, Double> sp = graph.shortestPath("A");
        System.out.println(sp);
    }

    private static void testMST() {
        Graph<Object, Double> graph = undirectedGraph(Data.MST_01);
        Set<Graph.EdgeInfo<Object, Double>> mst = graph.mst();
        for (Graph.EdgeInfo<Object, Double> edgeInfo : mst) {
            System.out.println(edgeInfo);
        }
    }

    private static void testTopo() {
        Graph<Object, Double> topo = directedGraph(Data.TOPO);
        List<Object> list = topo.topologiccalSort();
        System.out.println(list);
    }

    private static void testDfs() {
        Graph<Object, Double> graph = directedGraph(Data.DFS_02);
        // graph.dfs("c");
    }

    private static void testBfs() {
        Graph<Object, Double> graph = directedGraph(Data.BFS_02);
        graph.bfs(0, val -> {
            System.out.println(val);
            return false;
        });
    }

    private static void test1() {
        // Graph<String, Integer> graph = new ListGraph<>();
        // graph.addEdge("V1", "V0", 9);
        // graph.addEdge("V1", "V2", 3);
        // graph.addEdge("V2", "V0", 2);
        // graph.addEdge("V2", "V3", 5);
        // graph.addEdge("V3", "V4", 1);
        // graph.addEdge("V0", "V4", 6);
        // // graph.bfs("V1");
        // System.out.println();
        // graph.print();
        //
        // graph.removeEdge("V0", "V4");
        // graph.print();
        //
        // graph.removeVertex("V0");
        // graph.print();
    }
}
